package 回溯算法;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class 组合Ⅲ {

    ArrayList<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combine(int n,int k){
        combineHelper2(n,k,1,0);
        return  result;
    }


    public void combineHelper2(int targetsum , int k ,int startIndex,int sum){
        //终止条件
        if (sum>targetsum)
            return;
        if (path.size()==k){
            if (sum ==  targetsum){
                result.add(new ArrayList<>(path));
                return;
            }
        }

        for (int i = startIndex;i<=9-(k-path.size())+1;i++){
            path.add(i);
            sum = sum + i;
            combineHelper2(targetsum,k,i+1,sum);
            //回溯
            path.removeLast();
            sum = sum - i;
        }

    }



}
